The present invention relates to multi-step digital signature systems. More particularly, the present invention relates to the management of the cryptographic keys used by certification authorities in multi-step digital signature systems.
Historically, written documents have been used by parties to record for future reference, or to conduct, commercial transactions when the parties are either unable, or find it undesirable, to meet face to face. Written contracts and other commercial papers continue to account for the bulk of all commercial transactions. As a result, procedures have been developed and currently exist for verifying the identity of the parties who have engaged in a written commercial transaction. The most fundamental of these procedures is the requirement that each ascribing party obtain a notary stamp verifying their individual handwritten signatures. By requiring that this procedure be used, each party to the transaction can be assured of having a signature of the other contracting party which, if the need arises, can be independently verified by handwriting analysis. Further, each party has the added security of the notary who attested to the signing of the document and who can be called upon to verify the identity of a signatory to the document.
As the availability of electronic communication technology continues to grow, companies, such as large financial institutions, have shown great interest in applying such technologies to their day-to-day commercial transactions. The use of such electronic communication technology advances in modern commercial transactions has been hampered, however, by the relative ease within which electronic messages can be altered or forged and the difficulty encountered in verifying the integrity of both the received information and the identity of the party sending the transmission. Without a means for verifying both the integrity and the author of an electronic transmission, such transmissions would be unusable in a commercial setting. As a result, systems have been proposed to prevent the alteration and forging of electronic communications and to enable the verification of the identity of the transmitting party. One class of these systems relies on asymmetric-key cryptography wherein each member of the system creates a private signature key, which is maintained in strict secrecy, and a corresponding verification key which is publicly disseminated. When a first party, called the signer, wishes to sign a message, the signature is created using the message and the signer""s own private signature key. A second party, called the verifier, can then verify the signature by performing a computation using the signer""s public verification key, the message, and the signature. The properties of these computations assure the verifier that the document has been unchanged since it was signed. One such asymmetric-key cryptographic system is described in U.S. Pat. No. 4,405,829.
One problem encountered in asymmetric-key cryptographic systems is the need for a verifier to be assured that a public verification key belongs to a particular signer. Without such assurance, a verifier will have no way of discerning whether a message has in fact been sent by an intended signer or has been xe2x80x9cforgedxe2x80x9d by a third party claiming to be that signer. This identification problem has been ameliorated in some systems through the use of a certification authority (CA). The CA produces a xe2x80x9crootxe2x80x9d verification key that is made widely available in a manner in which users can be assured that they have a correct copy of the root verification key. Then a signer can have their verification key xe2x80x9ccertifiedxe2x80x9d (i.e., signed) by the CA, specifically by the CA root signature key. After verifying the signature on the document, a verifier can also verify the signature on the signer""s verification key and is thereby assured of the identity of the signer.
The strength of the foregoing cryptographic system typically resides in the computational infusibility of deriving a signature key from knowledge of either the verification key or signed messages. Thus, so long as the signature key is kept secret, the signers have some assurance that documents cannot be forged in their name, and the verifiers have some assurance that documents bearing the electronic signature of the signer were in fact generated by the signer.
It is critical in these systems, however, that the respective signature keys of the signer and CA continue to be maintained in strict secrecy. Any compromise of the secrecy of these keys results in a breakdown of the integrity of the system. If a user""s signature key is compromised, the CA must be notified to revoke the certificate and reissue a new one. If a CA""s private signature key is compromised, all users who might rely on that key must be notified, all outstanding certificates must be revoked, the CA must generate a new asymmetric key pair, all users must be recertified, and the CA must broadly distribute its new public verification key. This is particularly a problem for the root verification key, because this key would likely be made available to, and potentially be relied upon by, millions of users. Such a loss can impose a great burden on the system. For such a key, a single fraudulent signature can cause substantial losses for a corporation.
In order to further ameliorate the problem of trying to protect a single private key, a system and method have been described for generating private key fragments for the root certification authority and then distributing these fragments amongst a number of members of a multi-step signing group. In accordance with this system and method, the private key for the root certification authority never exists in toto at any time. This system and method are disclosed in the co-pending U.S. patent application Ser. No. 08/462,430 (the ""430 application), filed Jun. 5, 1995.
In the system and method of the ""430 application, a private root signature key is fragmented and each of the fragments is distributed to a different member of a signature group. The message to be signed is distributed to each of the members of the signature group, either serially or in parallel, and the message is signed by each member using its fragment of the private root signature key. When a message has been signed by all members and thus, using all fragments, a final signature is formed which can be verified using a single public verification key. Further, because all fragments of the private root signature key are maintained in separate devices at separate locations at all times, security of the key is enhanced.
Each member of the multi-step signature group takes significant precautions to maintain the secrecy of the key fragment in their possession. This makes it physically infeasible to acquire all of the private key fragments and, because it is computationally infeasible to derive the signature key from the verification key or from a set of messages signed with the signature key, this system offers a greater barrier to would be adversaries.
The foregoing multi-step signature system and method represents a significant improvement over prior asymmetric-key cryptographic systems. A loss of one or more, but less than some specified amount k, of the key fragments will not compromise the integrity of a multi-step system. Improvements to the foregoing system are still desirable, however, for changing the key fragments in response to system events such as the actual or suspected compromise of a key, the addition or removal of key fragment holders, the need to modify the key fragments, a change in the number of fragment holders required to sign, or a loss of a key fragment. Using current, standard technology, such events will require generation of new CA keys, revocation and reissuance of all certificates, redistribution of the CA""s new public verification key, a change of the private and public keys and notification to all potentially affected users. A need still exists, therefore, for a system and method for adapting to system events by changing key fragments without the need for changing the xe2x80x9crootxe2x80x9d verification key.
There are additional improvements that would be highly desirable for root CA multi-step signature systems or for any multi-step signature system in which the verification key must remain unchanged for an extended period of time. In particular, in an n-of-n multi-step root CA (where all n fragments of the root key are required to form a signature), it is desirable to securely backup the fragments in a safe and secure manner. Without a backup of the key fragments, the loss of a single fragment would make it impossible to sign anything new with that signature key.
Further, the system should allow for a change of the root keys on a routine basis. In particular, the system should allow for a change of key length so that security can be improved over time. Older devices may not be capable of handling the new key length however. A method to replace the root verification, key while causing as little disruption as possible, is therefore desirable.
The present invention responds to the needs of the foregoing multi-step digital signature systems. In its apparatus aspects a multi-step digital signature system is provided which includes a distributed certifying authority having a plurality of certifying authority members. Approval of a plurality of the plurality of certifying authority members is required in order to generate a digital signature for the distributed certifying authority. The distributed certifying authority may be one of a plurality of certifying authorities communicating to form a plurality of hierarchical certifying tiers.
In its process aspects, a method for decreasing the verification chain length in a hierarchical digital signature system is provided wherein a signature certificate for a user is obtained from a certifying authority at a first tier of the hierarchical digital signature system. The signature certificate from the first tier certifying authority is then presented to a higher tier certifying authority which issues a certificate authenticating the signature of the first tier certifying authority. The user then presents a verifier with the authenticating certificate of the higher tier certifying authority.
In its process aspects, a method is also provided for generating a digital signature in a n-of-n multi-step digital signature system having n certifying authority members in a distributed certifying authority wherein a message (m), to be signed, is received at the distributed certifying authority. The message is distributed to each of the n certifying authority members who then prepare separate messages (HASHr). The messages HASHr are prepared by selecting a random number (k) from which a value (r) is calculated using the function
r=gkD(m, HASH) mod p.
The HASH of the value r (HASH r) is then calculated. The HASHr value calculated by each of the certifying authority members are then distributed to the other nxe2x88x921 certifying authority members. The r value is then distributed: by each certifying authority member to the other nxe2x88x921 certifying authority members and the r values are confirmed using the function SHA(r)=HASHr. A composite r value is then computed at each of the certifying authority members as the product of all of the r values and a signature fragment value is computed by each certifying authority member using the composite r value.
In its process aspects a method of identifying the k members that participated in generating a signature in a k-of-n multi-step digital signature system is also provided wherein a set of n bits are appended to the end of a message to be signed. Each of the n bits, which are associated with one of the n members of the k-of-n multi-step digital signature system, are used to indicate which k members participated in generating a signature.
It is an object of the present invention to provide a multi-step digital signature system.
It is a further object of the present invention to provide a method for protecting the private key of a root certification authority.
It is a further object of the present invention to provide a multi-step digital signature system capable of changing the number of key fragment members.
It is a further object of the present invention to provide a k-of-n multi-step digital signature system capable of modifying the value of k without the need for changing the public key.
It is a further object of the present invention to provide a k-of-n multi-step digital signature system in which it can be determined which k members signed a particular document.
It is a further object of the present invention to provide a multi-step digital signature system capable of recovering from a loss of a key fragment without the need for changing the public key.
It is a further object of the present invention to provide a method for decreasing the length of a verification chain.
It is a further object of the present invention to provide a method of changing the fragments of the private key without the need for changing the public key.
It is a further object of the-present invention to provide a method for backing up the fragments in a multi-step digital signature system.
It is a further object of the present invention to provide a method for changing the root certification authority public key.
With these and other objects, advantages and features of the invention that may become hereinafter apparent, the nature of the invention may be more clearly understood by reference to the following detailed description of the invention, the appended claims, and to the several drawings attached herein.